package ljl.alg.wangzheng_camp.round1.tree;

import commons.TreeNode;

import java.util.LinkedList;

public class _513_find_bottom_left {
    
    /**
     * 虽然返回了 8848 这个吉利的数字
     * 但方法还是笨逼的要死
     * */
    public int findBottomLeftValue3(TreeNode root) {
        LinkedList<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            
            int res = 0;
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                if (i == 0) res = node.val;
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
            if (q.size() == 0) return res;
        }
        return 0;
    }
    
    /**
     * 从右向左遍历就行了，脑子不可以太死板
     * */
    public int findBottomLeftValue1(TreeNode root) {
        LinkedList<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int ret = root.val;
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node.right != null) q.offer(node.right);
            if (node.left != null) q.offer(node.left);
            ret = node.val;
        }
        return ret;
    }
    
    /**
     * 这个办法难道是最快的？
     * 目前来说，是
     * */
    int res;
    int highest;
    public int findBottomLeftValue(TreeNode root) {
        dfs(root, 0);
        return res;
    }
    void dfs(TreeNode root, int height) {
        if (root == null) return;
        height++;
        dfs(root.left, height);
        dfs(root.right, height);
        if (height > highest) {
            highest = height;
            res = root.val;
        }
    }
}
